package com.origin.niuke.dfs;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/6/18 10:19
 * 加起来和为目标值的组合(二)
 * 算法：回溯
 */
public class NC46 {

    ArrayList<ArrayList<Integer>> ans;
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        if (num == null || num.length == 0 || target <= 0) return ans;
        ans = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        Arrays.sort(num);
        dfs(0, num, target, list);
        return ans;
    }
    void dfs(int start, int[] num, int target, List<Integer> list) {
        if (target == 0) {
            ans.add(new ArrayList<>(list));
            return;
        }
        if (start >= num.length) return;
        for (int i = start; i < num.length; i++) {
            if (i > start && num[i] == num[i - 1]) continue;
            if (num[i] > target) break;
            list.add(num[i]);
            dfs(i + 1, num, target - num[i], list);
            list.remove(list.size() - 1);
        }
    }

}
